競プロ典型 90 問 006

(工事中)

解き方

解答例

下は上記の方法で解いたときの提出結果である。また、その提出の際に提出したソースコードをその下に転記する。

code: C

int main () {

int n = 0;

int k = 0;

int res = 0;

int ans_idx = 0;

res = scanf("%d", &n);

res = scanf("%d", &k);

res = scanf("%s", s);

for (int i = 0; i < n; i++) {

ans_idx--;

}

if(ans_idx < k) {

ans_idx++;

}

}

printf("%s\n", ans);

return 0;

}

私の提出一覧

table: submissions_atcoder_typical90_006

提出のURL 提出時刻 結果 備考

感想

ローカルにおいてあったzakkan.txt（雑感）に書かれていたこと

006 - Smallest Subsequence（★5）

日時: 2021-05-03 16:52:50

解説では前計算をする賢い方法が載っていたが、私の方法は少し違った。

私は単純に対象の文字列を頭から見ていき、小さい文字を順番に記憶していった。

部分文字列は順序は保存されるが連続していなくともよいという条件なので、

それより小さい文字が後から出てきた時点で答えに含まれないことが確定する。

そのため答えに含まれないことが確定した分だけ（つまり今注目している文字より

小さい文字が出てくるまで）記憶していた答え候補の添字を巻き戻す。

※最後の方に頭まで巻き戻してしまったりすると答えの文字数が足りなくなるため、

正確に言うと、どこまで巻き戻すかの条件に残り文字数に関する条件も必要

記憶しておく答え候補の長さが最大K であるので、計算量はO(NK) になりそうだが、

巻き戻すのは上で書いたとおり答えに含まれないと確定した分だけなので、

O(N) となることがわかる